﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习八月份
{
    public class Solution84
    {
        public int LargestRectangleArea1(int[] heights)
        {

            //使用和11. 盛最多水的容器一样的双指针
            //方法错误，中间有低的，无法形成矩形
            int len = heights.Length;
            int res = 0;
            int left = 0;
            int right = len - 1;

            while (left <= right)
            {


                int lower = Math.Min(heights[left], heights[right]);
                int curArea = lower * (right - left + 1);

                Console.WriteLine("   left   " + left + "   right   " + right + "   curArea   " + curArea);

                if (heights[left] < heights[right])
                {
                    left++;
                }
                else
                {
                    right--;
                }

                res = Math.Max(res, curArea);


            }
            return res;

        }


        public int LargestRectangleArea(int[] heights)
        {

            //单调栈
            int len = heights.Length;
            if (len == 1)
            {
                return heights[0];
            }
            int res = 0;

            Stack<int> stackLeft = new Stack<int>();
            int[] leftH = new int[len ];//存放左边比自己小的柱子的编号，左边比自己大的柱子不会有贡献（自己是高）
            //stackLeft.Push(0);
            //leftH[0] = -1;
            for (int i = 0; i < len; i++)
            {
                while (stackLeft.Count > 0 && heights[i] <= heights[stackLeft.Peek()])
                {
                    stackLeft.Pop();//出栈的都是比当前大的
                                    //为什么可以出栈，也就是丢弃，两种情况，
                                    //栈顶的数字比当前数字小，那么栈顶就是需要的数字
                                    //栈顶的数字比当前数字大，被栈顶弹掉的数字比栈顶还大，那么栈顶前面的数字才是需要的数字
                }
                if(stackLeft.Count > 0)
                {
                    leftH[i] = stackLeft.Peek();
                }
                else
                {
                    leftH[i] = -1;    //这个时候可能栈空，放一个特别小的数字-1,代表左边没有比自己小的
                }
            

                stackLeft.Push(i);


            }
            Stack<int> stackRight = new Stack<int>();
            int[] RightH = new int[len ];//存放右边比自己小的柱子的编号，右边比自己大的柱子不会有贡献（自己是高）
           
                for (int i = len - 1; i >= 0; i--)
            {
                while (stackRight.Count > 0 && heights[i] <= heights[stackRight.Peek()])
                {
                    stackRight.Pop();//出栈的都是比当前大的
                                     //为什么可以出栈，也就是丢弃，两种情况，
                                     //栈顶的数字比当前数字小，那么栈顶就是需要的数字
                                     //栈顶的数字比当前数字大，被栈顶弹掉的数字比栈顶还大，那么栈顶前面的数字才是需要的数字
                }
                if (stackRight.Count > 0)
                {
                    RightH[i] = stackRight.Peek();
                }
                else//这里已经完成初始化了
                {
                    RightH[i] = len;    //这个时候可能栈空，放一个特别小的数字-1,代表左边没有比自己小的
                }

                stackRight.Push(i);


            }


            for (int i = 0; i < len; i++)
            {
                int myleft = leftH[i] + 1;
                int myright = RightH[i] - 1 ;
                int area = (myright - myleft+1) * heights[i];
                res = Math.Max(area, res);


            }
            return res;
        }
    }

    class Program84
    {

        static void Main84(string[] args)
        {

            int[] heights = [2, 1, 5, 6, 2, 3];

            Solution84 solution = new Solution84();
            int res = solution.LargestRectangleArea(heights);
            Console.WriteLine("res   " + res);
        }
    }
}
